package leetcode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author Liangyaoyun
 */
public class leetCode10 {
    public boolean isMatch(String s, String p) {
        char[] charS = s.toCharArray();
        char[] charP = p.toCharArray();
        Queue<Character> queueS = new LinkedList<>();
        Queue<Character> queueP = new LinkedList<>();
        Stack<Character> before = new Stack<>();
        //存放特殊字符
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            queueS.add(charS[i]);
        }
        for (int i = 0; i < p.length(); i++) {
            queueP.add(charP[i]);
        }
        //当判断的两个字符不为空
        while (!queueP.isEmpty() && !queueS.isEmpty()) {
            //当字符匹配失败时，判断是否是特殊字符
            if (queueP.peek() != queueS.peek()) {
                //如果p是特殊字符’.‘，则入栈，并且无论s中队头是什么，都应该弹出一个
                if (queueP.peek() == '.') {
                    stack.add(queueP.poll());
                    before.add(queueS.poll());
                    continue;
                } //
                else if (queueP.peek() == '*') {
                    if (!stack.isEmpty()) {
                        //如果栈p不为空，判断里面的元素是什么
                        if (stack.peek() == '.') {
                            //如果s还存在字符，将它弹出压入before栈中
                            if (!queueS.isEmpty()) {
                                before.add(queueS.poll());
                            }
                            //判断新的队头元素是否跟上一个元素相等，如果相等继续出队
                            while (queueS.peek()==before.peek()){
                                before.add(queueS.poll());
                            }
                            //最后将特殊字符’.‘出栈
                            stack.pop();
                        }//如果特殊字符栈中不是特殊字符'.'，进行进一步判断
                        else {
                            //如果字符栈中不是空,且字符栈顶等于s队列头元素，且特殊字符栈顶等于s的队列头元素
                            if (!before.isEmpty() && before.peek() == queueS.peek() && stack.peek() == queueS.peek()) {
                                //如果队列不为空则将s中的元素压入栈中
                                if (!queueS.isEmpty()) {
                                    before.add(queueS.poll());
                                }
                            }
                        }
                    }
                }
            }
            //匹配成功
            else if (queueP.peek() == queueS.peek()) {
                before.add(queueS.poll());
            }
            stack.add(queueP.poll());
        }
        if(queueS.isEmpty()){
            return true;
        }
        if (queueP.isEmpty() && queueS.isEmpty()) {
            return true;
        } else if (!queueS.isEmpty() && queueP.isEmpty()) {
            return false;
        } else {
            return false;
        }
    }



    public static void main(String[] args) {
        leetCode10 leetCode10 = new leetCode10();
        String s = "aaa";
        String p = "a*a";
        System.out.println(leetCode10.isMatch(s, p));
    }
}
